public class MergeBU {
    private static Comparable[] aux;

    public static void sort(Comparable[] a){
        //进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz=sz+sz) {
            for (int lo = 0; lo < N-sz; lo+=sz+sz) {
                merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
            }
        }
    }
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //将a[lo..mid]和a[mid+1..hi]归并
        int i =lo,j=mid+1;
        for (int k = lo; k <= hi; k++) {
            //将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            //归并回到a[lo..hi]
            if(i>mid) a[k]=aux[j++];
            else if(j>hi) a[k]=aux[i++];
            else if (less(aux[j],aux[i]))a[k] = aux[j++];
            else a[k]= aux[i++];
        }
    }
    private static boolean less(Comparable v,Comparable w){   //对比大小
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){   //进行交换
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    private static void show(Comparable[] a){   //显示每次交换情况
        for(int i = 0 ;i<a.length;i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }
    public static boolean isSorted(Comparable[] a){    //判断是否交换
        for(int i = 1;i<a.length;i++)
            if(less(a[i],a[i-1]))
                return false;
        return true;
    }
}
